import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-19
 * Time: 23:15
 */



class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {

//  方法一: BFS
    // public List<Integer> largestValues(TreeNode root) {
    //     List<Integer> list=new ArrayList<>();
    //     if(root==null){
    //         return list;
    //     }
    //     Deque<TreeNode> queue=new LinkedList<>();
    //     queue.add(root);
    //     while(!queue.isEmpty()){
    //         int size=queue.size();
    //         int max=Integer.MIN_VALUE;
    //         for(int i=0;i<size;i++){
    //             TreeNode temp=queue.poll();
    //             max=Math.max(max, temp.val);
    //             if(temp.left!=null){
    //                 queue.add(temp.left);
    //             }
    //             if(temp.right!=null){
    //                 queue.add(temp.right);
    //             }
    //         }
    //         list.add(max);
    //     }
    //     return list;
    // }

    // 方法二: DFS
    public List<Integer> largestValues(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        List<Integer> ans=new ArrayList<>();
        // 根节点表示第 0 层
        dfs(ans, 0,root);
        return ans;
    }

    public void dfs(List<Integer> ans, int height, TreeNode root){
        if(height==ans.size()){
            // 如果高度与结果集的大小相同, 说明这个节点是这层的第一个节点, 直接添加进去
            ans.add(root.val);
        }else{
            // 否则需要与该层之前的最大值进行比较
            // 注意这里面是 ans.get(height), 不能是 ans.get(ans.size()-1),
            // 因为 ans 里面可能已经放了许多的值, 但是你要替换的是 height 下标的
            // 并不是ans 的 size一直 = height+1
            ans.set(height, Math.max(root.val, ans.get(height)));
        }
        if(root.left!=null){
            dfs(ans, height+1, root.left);
        }
        if(root.right!=null){
            dfs(ans, height+1, root.right);
        }
    }
}